﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AI
{
    // http://www.interact-sw.co.uk/iangblog/2004/09/16/permuterate



    public class PermuteUtils
    {


        // Print out the permutations of the input 
        public static List<List<T>> ShowPermutations<T>( IEnumerable<T> input, int count)
        {
            //경우의수를 저장할놈
            List<List<T>> PermuList = new List<List<T>>();

            foreach (IEnumerable<T> permutation in PermuteUtils.Permute<T>(input, count))
            {

                List<T> pathInfo = new List<T>();

                //스타트 저장
                //Permu.Add(sIndex);

                foreach (T i in permutation)
                {
                    pathInfo.Add(i);

                    //Console.Write(" " + i);
                }

                // 목적지 저장
                //pathInfo.Add(eIndex);

                PermuList.Add(pathInfo);

            }

            return PermuList;
        }




        // Returns an enumeration of enumerators, one for each permutation
        // of the input.
        public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count)
        {
            if (count == 0)
            {
                yield return new T[0];
            }
            else
            {
                int startingElementIndex = 0;
                foreach (T startingElement in list)
                {
                    IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex);

                    foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1))
                    {
                        yield return Concat<T>(
                            new T[] { startingElement },
                            permutationOfRemainder);
                    }
                    startingElementIndex += 1;
                }
            }
        }

        // Enumerates over contents of both lists.
        public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b)
        {
            foreach (T item in a) { yield return item; }
            foreach (T item in b) { yield return item; }
        }

        // Enumerates over all items in the input, skipping over the item
        // with the specified offset.
        public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip)
        {
            int index = 0;
            foreach (T item in input)
            {
                if (index != indexToSkip) yield return item;
                index += 1;
            }
        }
    }
//The following code tries the code out on a list of ints and a list of strings.

//class App
//{
//    static void Main(string[] args)
//    {
//        int[] intInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//        ShowPermutations<int>(intInput, 2);

//        string[] stringInput = { "Hello", "World", "Foo" };
//        ShowPermutations<string>(stringInput, 3);

//    }

//    // Print out the permutations of the input 
//    static void ShowPermutations<T>(IEnumerable<T> input, int count)
//    {
//        foreach (IEnumerable<T> permutation in PermuteUtils.Permute<T>(input, count))
//        {
//            foreach (T i in permutation)
//            {
//                Console.Write(" " + i);
//            }
//            Console.WriteLine();
//        }
//    }
//}

}
